{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Restore the Array From Adjacent Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: restoreArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从相邻元素对还原数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>存在一个由 <code>n</code> 个不同元素组成的整数数组 <code>nums</code> ，但你已经记不清具体内容。好在你还记得 <code>nums</code> 中的每一对相邻元素。</p>\n",
    "\n",
    "<p>给你一个二维整数数组 <code>adjacentPairs</code> ，大小为 <code>n - 1</code> ，其中每个 <code>adjacentPairs[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> 表示元素 <code>u<sub>i</sub></code> 和 <code>v<sub>i</sub></code> 在 <code>nums</code> 中相邻。</p>\n",
    "\n",
    "<p>题目数据保证所有由元素 <code>nums[i]</code> 和 <code>nums[i+1]</code> 组成的相邻元素对都存在于 <code>adjacentPairs</code> 中，存在形式可能是 <code>[nums[i], nums[i+1]]</code> ，也可能是 <code>[nums[i+1], nums[i]]</code> 。这些相邻元素对可以 <strong>按任意顺序</strong> 出现。</p>\n",
    "\n",
    "<p>返回 <strong>原始数组</strong><em> </em><code>nums</code><em> </em>。如果存在多种解答，返回 <strong>其中任意一个</strong> 即可。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>adjacentPairs = [[2,1],[3,4],[3,2]]\n",
    "<strong>输出：</strong>[1,2,3,4]\n",
    "<strong>解释：</strong>数组的所有相邻元素对都在 adjacentPairs 中。\n",
    "特别要注意的是，adjacentPairs[i] 只表示两个元素相邻，并不保证其 左-右 顺序。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>adjacentPairs = [[4,-2],[1,4],[-3,1]]\n",
    "<strong>输出：</strong>[-2,4,1,-3]\n",
    "<strong>解释：</strong>数组中可能存在负数。\n",
    "另一种解答是 [-3,1,4,-2] ，也会被视作正确答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>adjacentPairs = [[100000,-100000]]\n",
    "<strong>输出：</strong>[100000,-100000]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums.length == n</code></li>\n",
    "\t<li><code>adjacentPairs.length == n - 1</code></li>\n",
    "\t<li><code>adjacentPairs[i].length == 2</code></li>\n",
    "\t<li><code>2 <= n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>5</sup> <= nums[i], u<sub>i</sub>, v<sub>i</sub> <= 10<sup>5</sup></code></li>\n",
    "\t<li>题目数据保证存在一些以 <code>adjacentPairs</code> 作为元素对的数组 <code>nums</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [restore-the-array-from-adjacent-pairs](https://leetcode.cn/problems/restore-the-array-from-adjacent-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [restore-the-array-from-adjacent-pairs](https://leetcode.cn/problems/restore-the-array-from-adjacent-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,1],[3,4],[3,2]]', '[[4,-2],[1,4],[-3,1]]', '[[100000,-100000]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        cache = collections.defaultdict(list)\n",
    "\n",
    "        for i, j in adjacentPairs:\n",
    "            cache[i].append(j)\n",
    "            cache[j].append(i)\n",
    "\n",
    "        res = [0 for _ in range(len(adjacentPairs)+1)]\n",
    "\n",
    "        for k, v in cache.items():\n",
    "            if len(v) == 1:\n",
    "                res[0] = k \n",
    "                break\n",
    "        \n",
    "        left, mid = float('-inf'), res[0]\n",
    "        for i in range(1, len(res)):\n",
    "            outs = cache[mid]\n",
    "            for j in outs:\n",
    "                if j != left:\n",
    "                    res[i] = j \n",
    "                    left, mid = mid, j\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        n=len(adjacentPairs)+1\n",
    "        g=defaultdict(list)\n",
    "        res=[None]*n\n",
    "        idx=0\n",
    "        for a,b in adjacentPairs:\n",
    "            g[a]+=[b]\n",
    "            g[b]+=[a]\n",
    "        for a in list(g.keys()):\n",
    "            if len(g[a])==1:\n",
    "                pre=-114514\n",
    "                while True:\n",
    "                    res[idx]=a\n",
    "                    idx+=1\n",
    "                    if idx==n:\n",
    "                        break\n",
    "                    if g[a][0]!=pre:\n",
    "                        a,pre=g[a][0],a\n",
    "                    else:\n",
    "                        a,pre=g[a][1],a\n",
    "                break \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, ps: List[List[int]]) -> List[int]:\n",
    "        m = defaultdict(list)\n",
    "        for i,p in enumerate(ps):\n",
    "            m[p[0]].append(i)\n",
    "            m[p[1]].append(i)\n",
    "        for k in m:\n",
    "            if len(m[k]) == 1:\n",
    "                cur = k\n",
    "                break\n",
    "        ss = [cur]\n",
    "        index = -1\n",
    "        while len(ss) != len(ps)+1:\n",
    "            index = m[cur][1]  if m[cur][0] == index else m[cur][0]\n",
    "            cur = ps[index][1] if ps[index][0] == cur else ps[index][0]\n",
    "            ss.append(cur)\n",
    "        return ss\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        neighbors = defaultdict(list)\n",
    "        indegree = defaultdict(int)\n",
    "\n",
    "        for u, v in adjacentPairs:\n",
    "            neighbors[u].append(v)\n",
    "            neighbors[v].append(u)\n",
    "            indegree[u] += 1\n",
    "            indegree[v] += 1\n",
    "        \n",
    "        visitied = defaultdict(bool)\n",
    "        n = len(adjacentPairs) + 1\n",
    "        res = [0] * n\n",
    "\n",
    "        for node, d in indegree.items():\n",
    "            if d == 1:\n",
    "                start = node\n",
    "                break\n",
    "\n",
    "        res[0] = start\n",
    "        res[1] = neighbors[start][0]\n",
    "        for i in range(2, n):\n",
    "            prev = res[i-1]\n",
    "            for node in neighbors[prev]:\n",
    "                if node != res[i-2]:\n",
    "                    res[i] = node\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        memo = defaultdict(list)\n",
    "        ends = set()\n",
    "\n",
    "        for adjacentPair in adjacentPairs:\n",
    "            fst = memo.get(adjacentPair[0], [])\n",
    "            snd = memo.get(adjacentPair[1], [])\n",
    "\n",
    "            fst.append(adjacentPair[1])\n",
    "            snd.append(adjacentPair[0])\n",
    "\n",
    "            memo[adjacentPair[0]] = fst\n",
    "            memo[adjacentPair[1]] = snd\n",
    "\n",
    "            if adjacentPair[0] in ends:\n",
    "                ends.remove(adjacentPair[0])\n",
    "            else:\n",
    "                ends.add(adjacentPair[0])\n",
    "\n",
    "            if adjacentPair[1] in ends:\n",
    "                ends.remove(adjacentPair[1])\n",
    "            else:\n",
    "                ends.add(adjacentPair[1])\n",
    "\n",
    "        cur = ends.pop()\n",
    "        end = ends.pop()\n",
    "        ans = [cur]\n",
    "        pre = -1\n",
    "        \n",
    "        while cur != end:\n",
    "            temp = memo[cur]\n",
    "            if temp[0] != pre:\n",
    "                pre = cur\n",
    "                cur = temp[0]\n",
    "            else:\n",
    "                pre = cur\n",
    "                cur = temp[1]\n",
    "            ans.append(cur)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        hashmap = {}\n",
    "        for pair in adjacentPairs:\n",
    "            x, y = pair\n",
    "            if x in hashmap and y in hashmap:\n",
    "                qx = hashmap.pop(x)\n",
    "                qy = hashmap.pop(y)\n",
    "                if qx[0] == x and qy[0] == y:\n",
    "                    hashmap.pop(qx[-1])\n",
    "                    hashmap.pop(qy[-1])\n",
    "                    qx.reverse()\n",
    "                    qx.extend(qy)\n",
    "                    hashmap[qx[0]] = qx\n",
    "                    hashmap[qx[-1]] = qx\n",
    "                elif qx[0] == x and qy[-1] == y:\n",
    "                    hashmap.pop(qx[-1])\n",
    "                    hashmap.pop(qy[0])\n",
    "                    qy.extend(qx)\n",
    "                    hashmap[qy[0]] = qy\n",
    "                    hashmap[qy[-1]] = qy\n",
    "                elif qx[-1] == x and qy[0] == y:\n",
    "                    hashmap.pop(qx[0])\n",
    "                    hashmap.pop(qy[-1])\n",
    "                    qx.extend(qy)\n",
    "                    hashmap[qx[0]] = qx\n",
    "                    hashmap[qx[-1]] = qx\n",
    "                elif qx[-1] == x and qy[-1] == y:\n",
    "                    hashmap.pop(qx[0])\n",
    "                    hashmap.pop(qy[0])\n",
    "                    qy.reverse()\n",
    "                    qx.extend(qy)\n",
    "                    hashmap[qx[0]] = qx\n",
    "                    hashmap[qx[-1]] = qx\n",
    "            elif x in hashmap:\n",
    "                q = hashmap.pop(x)\n",
    "                if q[0] == x:\n",
    "                    q.appendleft(y)\n",
    "                elif q[-1] == x:\n",
    "                    q.append(y)\n",
    "                hashmap[y] = q\n",
    "            elif y in hashmap:\n",
    "                q = hashmap.pop(y)\n",
    "                if q[0] == y:\n",
    "                    q.appendleft(x)\n",
    "                elif q[-1] == y:\n",
    "                    q.append(x)\n",
    "                hashmap[x] = q\n",
    "            else:\n",
    "                q = deque([x, y])\n",
    "                hashmap[x] = q\n",
    "                hashmap[y] = q\n",
    "\n",
    "        return list(list(hashmap.values())[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        n = len(adjacentPairs) + 1\n",
    "        g = defaultdict(list)\n",
    "        ind = defaultdict(int)\n",
    "        for u, v in adjacentPairs:\n",
    "            ind[u] += 1\n",
    "            ind[v] += 1\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        ans = []\n",
    "        node = [k for k, v in ind.items() if v == 1][0]\n",
    "        q = deque([node])\n",
    "        s = set([node])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            ans.append(node)\n",
    "            for ch in g[node]:\n",
    "                if ch not in s:\n",
    "                    s.add(ch)\n",
    "                    q.append(ch)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        graph = defaultdict(list)\n",
    "        indegree = defaultdict(int)\n",
    "        for pair in adjacentPairs:\n",
    "            graph[pair[0]].append(pair[1])\n",
    "            graph[pair[1]].append(pair[0])\n",
    "            indegree[pair[0]] += 1\n",
    "            indegree[pair[1]] += 1\n",
    "        for i in indegree:\n",
    "            if indegree[i] == 1:\n",
    "                num = [i, graph[i][0]]\n",
    "                break\n",
    "        for i in range(len(adjacentPairs)-1):\n",
    "            first, second = graph[num[-1]]\n",
    "            if first == num[-2]:\n",
    "                num.append(second)\n",
    "            else:\n",
    "                num.append(first)\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        head = set()\n",
    "        mem = {}\n",
    "        # 遍历相邻数组，找到开头和每个元素的相邻元素\n",
    "        for u,v in adjacentPairs:\n",
    "            if u in mem:\n",
    "                head.remove(u)\n",
    "                mem[u].append(v)\n",
    "            else:\n",
    "                head.add(u)\n",
    "                mem[u] = [v]\n",
    "            if v in mem:\n",
    "                head.remove(v)\n",
    "                mem[v].append(u)\n",
    "            else:\n",
    "                head.add(v)\n",
    "                mem[v] = [u]\n",
    "        last = None\n",
    "        cur = head.pop()\n",
    "        ans = [cur]\n",
    "        flg = 1\n",
    "        while flg:\n",
    "            for x in mem[cur]:\n",
    "                if x!=last:\n",
    "                    ans.append(x)\n",
    "                    break\n",
    "            else:\n",
    "                flg = 0\n",
    "            last = cur\n",
    "            cur = x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        num1  = set()\n",
    "        dict1 = dict()\n",
    "        dict2 = dict()\n",
    "        n = len(adjacentPairs)\n",
    "        for x,y in adjacentPairs:\n",
    "            if x in num1:\n",
    "                num1.discard(x)\n",
    "            else:\n",
    "                num1.add(x)\n",
    "            if y in num1:\n",
    "                num1.discard(y)\n",
    "            else:\n",
    "                num1.add(y)\n",
    "            if x not in dict1:\n",
    "                dict1[x] = y\n",
    "            else:\n",
    "                dict2[x] = y\n",
    "            if y not in dict1:\n",
    "                dict1[y] = x\n",
    "            else:\n",
    "                dict2[y] = x\n",
    "\n",
    "        first,end = list(num1)\n",
    "        ans = [first]\n",
    "        temp = {first}\n",
    "        while True:\n",
    "            if first in dict1:\n",
    "                if dict1[first] in temp:\n",
    "                    first = dict2[first]\n",
    "                else:\n",
    "                    first = dict1[first]\n",
    "            else:\n",
    "                first = dict2[first]\n",
    "            ans.append(first)\n",
    "            temp.add(first)\n",
    "            if first == end:\n",
    "                return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        n = len(adjacentPairs) + 1\n",
    "        g = defaultdict(list)\n",
    "        nums = []\n",
    "        ini = -1\n",
    "        for u,v in adjacentPairs:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "            ini = u\n",
    "        pos = dict()\n",
    "        left,right = -1,-1\n",
    "        pos[ini] = 0\n",
    "        cur_l,cur_r = -1,-1\n",
    "        if len(g[ini])==1:\n",
    "            pos[g[ini][0]] = 1\n",
    "            left,right = 0, 1\n",
    "            cur_l,cur_r = ini,g[ini][0]\n",
    "        else:\n",
    "            pos[g[ini][0]] = -1\n",
    "            pos[g[ini][1]] = 1\n",
    "            left,right = -1, 1\n",
    "            cur_l,cur_r = g[ini][0],g[ini][1]\n",
    "\n",
    "        while len(pos)<n:\n",
    "            if not len(g[cur_l])==1:\n",
    "                adj1,adj2 = g[cur_l]\n",
    "                new = adj1 if adj2 in pos else adj2\n",
    "                pos[new] = left - 1\n",
    "                left -= 1\n",
    "                cur_l = new\n",
    "            if not len(g[cur_r])==1:\n",
    "                adj1,adj2 = g[cur_r]\n",
    "                new = adj1 if adj2 in pos else adj2\n",
    "                pos[new] = right + 1\n",
    "                right += 1\n",
    "                cur_r = new\n",
    "            pass\n",
    "\n",
    "        idx2val = {v:k for k,v in pos.items()}\n",
    "        idx_list = [idx for idx in idx2val.keys()]\n",
    "        idx_list.sort()\n",
    "        for idx in idx_list:\n",
    "            nums.append(idx2val[idx])\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.neighbors = []\n",
    "        self.next = None\n",
    "\n",
    "    def adjacent(self, node):\n",
    "        self.neighbors.append(node)\n",
    "\n",
    "    def update(self, _from):\n",
    "        if len(self.neighbors) == 1:\n",
    "            self.next = None\n",
    "        else:\n",
    "            for n in self.neighbors:\n",
    "                if n != _from:\n",
    "                    self.next = n\n",
    "                    break\n",
    "\n",
    "    def is_head(self):\n",
    "        if len(self.neighbors) > 1:\n",
    "            return False\n",
    "        self.next = self.neighbors[0]\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        nodes = dict()\n",
    "        for pair in adjacentPairs:\n",
    "            if pair[0] not in nodes:\n",
    "                nodes[pair[0]] = Node(pair[0])\n",
    "            if pair[1] not in nodes:\n",
    "                nodes[pair[1]] = Node(pair[1])\n",
    "            node0 = nodes[pair[0]]\n",
    "            node1 = nodes[pair[1]]\n",
    "            node0.adjacent(node1)\n",
    "            node1.adjacent(node0)\n",
    "        for node in nodes.values():\n",
    "            if node.is_head():\n",
    "                head = node\n",
    "                break\n",
    "        result = []\n",
    "        curr = head\n",
    "        while curr:\n",
    "            result.append(curr.val)\n",
    "            next = curr.next\n",
    "            if next:\n",
    "                next.update(curr)\n",
    "            curr = next\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        nm1 = len(adjacentPairs)\n",
    "        ans = [0] * (nm1+1)\n",
    "        from collections import defaultdict\n",
    "        num2pairs = defaultdict(lambda: list())\n",
    "        occured = set()\n",
    "        for numl, numr in adjacentPairs:\n",
    "            num2pairs[numl].append((numl, numr))\n",
    "            num2pairs[numr].append((numr, numl))\n",
    "        ends = []\n",
    "        for num in num2pairs:\n",
    "            if len(num2pairs[num])==1:\n",
    "                ends.append(num)\n",
    "        assert(len(ends)==2)\n",
    "        ans[0] = ends[0]\n",
    "        ans[-1] = ends[1]\n",
    "        occured.add(ans[0])\n",
    "        occured.add(ans[-1])\n",
    "        prev_num = ans[0]\n",
    "        for i in range(1, len(ans)-1):\n",
    "            for pair in num2pairs[prev_num]:\n",
    "                if not pair[1] in occured:\n",
    "                    ans[i] = pair[1]\n",
    "                    occured.add(pair[1])\n",
    "                    prev_num = pair[1]\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        dic = {}\n",
    "        for a,b in adjacentPairs:\n",
    "            if a not in dic.keys():\n",
    "                dic[a] = set()\n",
    "            if b not in dic.keys():\n",
    "                dic[b] = set()\n",
    "            dic[a].add(b)\n",
    "            dic[b].add(a)\n",
    "        \n",
    "        # 找到头或者尾，连接数最少\n",
    "        start = min(dic.keys(), key=lambda x:(len(dic[x]), x))\n",
    "        visited = set()\n",
    "        visited.add(start)\n",
    "        ans = [start]\n",
    "        cur = start\n",
    "\n",
    "\n",
    "        while len(ans) < len(dic.keys()):\n",
    "            # 其实每个点最多有两个连接，去掉已见过的，就只剩一个\n",
    "            cur = (dic[cur] - visited).pop()\n",
    "            visited.add(cur)\n",
    "            ans.append(cur)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        dic = defaultdict(set)\n",
    "        for a, b in adjacentPairs:\n",
    "            dic[a].add(b)\n",
    "            dic[b].add(a)\n",
    "        start = min(dic.keys(), key=lambda x: (len(dic[x]), x))\n",
    "        visited = {start}\n",
    "        res = [start]\n",
    "        curr = start\n",
    "        while len(res) < len(dic.keys()):\n",
    "            curr = (dic[curr] - visited).pop()\n",
    "            visited.add(curr)\n",
    "            res.append(curr)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        start = set()\n",
    "        adjacent = collections.defaultdict(set)\n",
    "        for u, v in adjacentPairs:\n",
    "            adjacent[u].add(v)\n",
    "            adjacent[v].add(u)\n",
    "            if len(adjacent[u]) == 1:\n",
    "                start.add(u)\n",
    "            else:\n",
    "                start.remove(u)\n",
    "            if len(adjacent[v]) == 1:\n",
    "                start.add(v)\n",
    "            else:\n",
    "                start.remove(v)\n",
    "        ans = [start.pop()]\n",
    "        ans.append(adjacent[ans[-1]].pop())\n",
    "        while len(ans) < len(adjacent):\n",
    "            cur = ans[-1]\n",
    "            num1 = adjacent[cur].pop()\n",
    "            num2 = adjacent[cur].pop()\n",
    "            ans.append(num1 if num1 != ans[-2] else num2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        d = collections.defaultdict(set)\n",
    "        c = collections.defaultdict(int)\n",
    "        for num1,num2 in adjacentPairs:\n",
    "            d[num1].add(num2)\n",
    "            d[num2].add(num1)\n",
    "            c[num1] += 1\n",
    "            c[num2] += 1\n",
    "            \n",
    "        for num in d:\n",
    "            if c[num] == 1:\n",
    "                p = num\n",
    "                break\n",
    "                \n",
    "        ans = [p,d[p].pop()]\n",
    "        x = set(ans)\n",
    "        \n",
    "        while c[ans[-1]] == 2:\n",
    "            for num in d[ans[-1]]:\n",
    "                if num in x:\n",
    "                    continue\n",
    "                x.add(num)\n",
    "                ans.append(num)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        g = {}  # graph \n",
    "        d = {}  # map_vertex_degree\n",
    "\n",
    "        for u, v in adjacentPairs:\n",
    "            g[u] = g.get(u, set()).union({v})\n",
    "            g[v] = g.get(v, set()).union({u})\n",
    "            d[u] = d.get(u, 0) + 1\n",
    "            d[v] = d.get(v, 0) + 1\n",
    "\n",
    "        for u, deg in d.items():\n",
    "            if deg == 1:\n",
    "                break\n",
    "\n",
    "        q = [u]\n",
    "        res = []\n",
    "        while len(q) != 0:\n",
    "            u = q.pop()\n",
    "            res.append(u)\n",
    "            d[u] -= 1\n",
    "            for v in g[u]:\n",
    "                if d[v] == 0:\n",
    "                    continue\n",
    "                d[v] -= 1\n",
    "                q.append(v)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        g = {}  # graph \n",
    "        d = {}  # map_vertex_degree\n",
    "\n",
    "        for u, v in adjacentPairs:\n",
    "            g[u] = g.get(u, set()).union({v})\n",
    "            g[v] = g.get(v, set()).union({u})\n",
    "            d[u] = d.get(u, 0) + 1\n",
    "            d[v] = d.get(v, 0) + 1\n",
    "\n",
    "        for u, deg in d.items():\n",
    "            if deg == 1:\n",
    "                break\n",
    "\n",
    "        visited = set()\n",
    "        q = [u]\n",
    "        res = []\n",
    "        while len(q) != 0:\n",
    "            u = q.pop()\n",
    "            res.append(u)\n",
    "            visited.add(u)\n",
    "            for v in g[u]:\n",
    "                if v in visited:\n",
    "                    continue\n",
    "                q.append(v)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        dic = collections.defaultdict(set)\n",
    "        for u, v in adjacentPairs[1:]:\n",
    "            dic[u].add((u,v))\n",
    "            dic[v].add((v,u))\n",
    "        \n",
    "        res = collections.deque(adjacentPairs[0])\n",
    "        \n",
    "        while dic:\n",
    "            u, v = res[0], res[-1]\n",
    "\n",
    "            if u in dic:\n",
    "                _, v = dic[u].pop()\n",
    "                res.appendleft(v)\n",
    "                dic[v].discard((v,u))                \n",
    "            elif v in dic:\n",
    "                _, u = dic[v].pop()\n",
    "                res.append(u)\n",
    "                dic[u].discard((u,v))\n",
    "            if not dic[u]:\n",
    "                del dic[u]\n",
    "            if not dic[v]:\n",
    "                del dic[v]\n",
    "        return list(res)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        numSet = set()\n",
    "        nxt = defaultdict(set)\n",
    "        \n",
    "        indegree = defaultdict(int)\n",
    "        for i,j in adjacentPairs:\n",
    "            nxt[i].add(j)\n",
    "            indegree[j]+=1\n",
    "            nxt[j].add(i)\n",
    "            indegree[i]+=1\n",
    "            numSet.add(i)\n",
    "            numSet.add(j)\n",
    "        startPoint = None\n",
    "        for e in indegree:\n",
    "            if indegree[e] == 1:\n",
    "                startPoint = e\n",
    "                break\n",
    "        ans = [startPoint]\n",
    "        visited = defaultdict(int)\n",
    "        while len(nxt[startPoint])>0 and visited[startPoint] == 0:\n",
    "            visited[startPoint] = 1\n",
    "            for e in nxt[startPoint]:\n",
    "                if visited[e] == 0:\n",
    "                    startPoint = e\n",
    "                    ans.append(startPoint)\n",
    "                    break\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        di = {}\n",
    "        for i, j in adjacentPairs:\n",
    "            if i not in di:\n",
    "                di[i] = {\"ad\": [], \"len\": 0}\n",
    "            if j not in di:\n",
    "                di[j] = {\"ad\": [], \"len\": 0}\n",
    "            di[i][\"ad\"].append(j)\n",
    "            di[j][\"ad\"].append(i)\n",
    "            di[i][\"len\"] += 1\n",
    "            di[j][\"len\"] += 1\n",
    "        print(di)\n",
    "        res = []\n",
    "        head = 0\n",
    "        front_head = 0\n",
    "        for j in di:\n",
    "            if di[j][\"len\"] == 1:\n",
    "                res.append(j)\n",
    "                res.append(di[j][\"ad\"][0])\n",
    "                front_head = j\n",
    "                head = di[j][\"ad\"][0]\n",
    "                break\n",
    "        print(res)\n",
    "        while len(res) < len(adjacentPairs) + 1:\n",
    "            print(front_head,head)\n",
    "            if di[head][\"ad\"][0] != front_head:\n",
    "                front_head = head\n",
    "                head = di[head][\"ad\"][0]\n",
    "                res.append(head)\n",
    "            else:\n",
    "\n",
    "                front_head = head\n",
    "                head = di[head][\"ad\"][1]\n",
    "                res.append(head)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        # 第一次提交卡39/46，超时，看来确实一个num只会出现一次。我这方法搭了matrix的话遍历matrix时间/空间复杂度是O(N^2)，\n",
    "        # 其实不用搭matrix，用adjacentPairs就行了（得改成双向的，两倍长度），改改\n",
    "        \n",
    "        \n",
    "#         # 变成图吧，然后找起点/终点\n",
    "#         # 没说数组元素num能不能相等，给的例子都是不等的，若不等则起点终点的num出现次数为1，\n",
    "#         # <s>若可能相等则起点终点num的出现次数为奇数（但不代表出现次数为奇数的num就是起点/终点）</s>若起点num=终点num则全是偶数了\n",
    "                \n",
    "#         # 假定不能相等\n",
    "#         start_end = set()\n",
    "#         num2idx = dict()\n",
    "#         idx2num = dict()\n",
    "#         idx = 0\n",
    "#         for pair in adjacentPairs:\n",
    "#             for num in pair:\n",
    "#                 if num not in start_end:\n",
    "#                     start_end.add(num)\n",
    "#                 else:\n",
    "#                     start_end.remove(num)\n",
    "                    \n",
    "#                 if num not in num2idx:\n",
    "#                     num2idx[num] = idx\n",
    "#                     idx2num[idx] = num\n",
    "#                     idx += 1        \n",
    "#         start, end = start_end\n",
    "        \n",
    "#         nums = len(adjacentPairs) + 1\n",
    "        \n",
    "#         matrix = [[float('inf')] * nums for _ in range(nums)]\n",
    "# #         for i in range(nums):\n",
    "# #             matrix[i][i] = 0\n",
    "            \n",
    "#         # 相邻的是1\n",
    "#         for pair in adjacentPairs:\n",
    "#             a, b = pair\n",
    "#             a_idx = num2idx[a]\n",
    "#             b_idx = num2idx[b]\n",
    "#             matrix[a_idx][b_idx] = 1\n",
    "#             matrix[b_idx][a_idx] = 1\n",
    "        \n",
    "        \n",
    "#         res = [start]\n",
    "#         cur_idx = num2idx[start]\n",
    "#         # 从起点开始走一遍，走过以后的格子又变成float('inf')\n",
    "#         for _ in range(nums - 1):\n",
    "#             for idx, connect in enumerate(matrix[cur_idx]):\n",
    "#                 if connect == 1:\n",
    "#                     break\n",
    "                    \n",
    "#             # 走过以后格子又变成float('inf')\n",
    "#             matrix[cur_idx][idx] = float('inf')\n",
    "#             matrix[idx][cur_idx] = float('inf')\n",
    "            \n",
    "#             res.append(idx2num[idx])\n",
    "#             cur_idx = idx\n",
    "            \n",
    "#         return res   \n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        # 其实不用搭matrix，用adjacentPairs就行了（得改成双向的，两倍长度），改改\n",
    "        start_end = set()\n",
    "        num2idx = dict()\n",
    "        idx2num = dict()\n",
    "        idx = 0\n",
    "        for pair in adjacentPairs:\n",
    "            for num in pair:\n",
    "                if num not in start_end:\n",
    "                    start_end.add(num)\n",
    "                else:\n",
    "                    start_end.remove(num)\n",
    "                    \n",
    "                if num not in num2idx:\n",
    "                    num2idx[num] = idx\n",
    "                    idx2num[idx] = num\n",
    "                    idx += 1        \n",
    "        start, end = start_end\n",
    "        \n",
    "        nums = len(adjacentPairs) + 1\n",
    "        \n",
    "        # connects代替matrix\n",
    "        connects = dict()\n",
    "        \n",
    "        for pair in adjacentPairs:\n",
    "            a, b = pair\n",
    "            a_idx = num2idx[a]\n",
    "            b_idx = num2idx[b]\n",
    "            \n",
    "            # 除了start和end节点，都是双向的\n",
    "            if a_idx in connects:\n",
    "                connects[a_idx] = [[a_idx, b_idx], connects[a_idx][0]] \n",
    "            else:\n",
    "                connects[a_idx] = [[a_idx, b_idx]]\n",
    "                \n",
    "            if b_idx in connects:\n",
    "                connects[b_idx] = [[b_idx, a_idx], connects[b_idx][0]] \n",
    "            else:\n",
    "                connects[b_idx] = [[b_idx, a_idx]]        \n",
    "        \n",
    "        res = [start]\n",
    "        cur_idx = num2idx[start]\n",
    "        # 从起点开始走一遍，走过以后的格子又变成float('inf')\n",
    "        for _ in range(nums - 1):\n",
    "            idx = connects[cur_idx][0][1]\n",
    "                    \n",
    "            # 走过的路径删去\n",
    "            connects[cur_idx].pop()\n",
    "            connects[idx].remove([idx, cur_idx])\n",
    "            \n",
    "            res.append(idx2num[idx])\n",
    "            cur_idx = idx\n",
    "            \n",
    "        return res   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.nodes = set()\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        node_map = {}\n",
    "        root_node = {}\n",
    "        for val1, val2 in adjacentPairs:\n",
    "            node1 = node_map.setdefault(val1, Node(val1))\n",
    "            node2 = node_map.setdefault(val2, Node(val2))\n",
    "\n",
    "            if val1 in root_node:\n",
    "                del root_node[val1]\n",
    "            else:\n",
    "                root_node[val1] = node1\n",
    "            if val2 in root_node:\n",
    "                del root_node[val2]\n",
    "            else:\n",
    "                root_node[val2] = node2\n",
    "\n",
    "            node1.nodes.add(node2)\n",
    "            node2.nodes.add(node1)\n",
    "\n",
    "        res = []\n",
    "        cache_set = set()\n",
    "\n",
    "        def get_next_node(nodes):\n",
    "            for next_node in nodes:\n",
    "                if next_node.val in cache_set:\n",
    "                    continue\n",
    "                return next_node\n",
    "            return None\n",
    "\n",
    "        _, node = root_node.popitem()\n",
    "        while node:\n",
    "            res.append(node.val)\n",
    "            cache_set.add(node.val)\n",
    "            node = get_next_node(node.nodes)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnDirectedEulerPath:\n",
    "    def __init__(self, n, pairs):\n",
    "        # 数组形式存储的有向连接关系\n",
    "        self.n = n\n",
    "        self.pairs = pairs\n",
    "        # 欧拉路径上的每条边和经过的几点\n",
    "        self.paths = list()\n",
    "        self.nodes = list()\n",
    "        self.exist = False\n",
    "        self.get_euler_path()\n",
    "        return\n",
    "\n",
    "    def get_euler_path(self):\n",
    "        # 存顶点的出入度\n",
    "        degree = [0]*self.n\n",
    "        # 存储图关系\n",
    "        edge = [defaultdict(int) for _ in range(self.n)]\n",
    "        for i, j in self.pairs:\n",
    "            degree[i] += 1\n",
    "            degree[j] += 1\n",
    "            edge[i][j] += 1\n",
    "            edge[j][i] += 1\n",
    "\n",
    "        # 寻找起始节点\n",
    "        starts = []\n",
    "        zero = 0\n",
    "        for i in range(self.n):\n",
    "            # 如果有节点出度比入度恰好多 1，那么只有它才能是起始\n",
    "            if degree[i] % 2:\n",
    "                starts.append(i)\n",
    "            else:\n",
    "                zero += 1\n",
    "        del degree\n",
    "\n",
    "        # 不存在欧拉路径\n",
    "        if not len(starts) == 2:\n",
    "            if zero != self.n:\n",
    "                return\n",
    "            starts = [0]\n",
    "\n",
    "        \"\"\"\n",
    "        改进前的深搜版本\n",
    "        def dfs(pre):\n",
    "            # 使用深度优先搜索（Hierholzer算法）求解欧拉通路\n",
    "            for nex in range(self.n):\n",
    "                while edge[pre][nex]:\n",
    "                    edge[pre][nex] -= 1\n",
    "                    edge[nex][pre] -= 1\n",
    "                    dfs(nex)\n",
    "                    self.nodes.append(nex)\n",
    "                    self.paths.append([pre, nex])\n",
    "            return\n",
    "\n",
    "        dfs(starts[0])\n",
    "        self.paths.reverse()\n",
    "        self.nodes.append(starts[0])\n",
    "        self.nodes.reverse()\n",
    "        \"\"\"\n",
    "        # 使用迭代版本Hierholzer算法计算\n",
    "        stack = [starts[0]]\n",
    "        while stack:\n",
    "            current = stack[-1]\n",
    "            next_node = None\n",
    "            for nex in edge[current]:\n",
    "                if edge[current][nex]:\n",
    "                    edge[current][nex] -= 1\n",
    "                    edge[nex][current] -= 1\n",
    "                    next_node = nex\n",
    "                    stack.append(next_node)\n",
    "                    break\n",
    "            if next_node is None:\n",
    "                self.nodes.append(current)\n",
    "                if len(stack) > 1:\n",
    "                    pre = stack[-2]\n",
    "                    self.paths.append([pre, current])\n",
    "                stack.pop()\n",
    "        self.paths.reverse()\n",
    "        self.nodes.reverse()\n",
    "        # 注意判断所有边都经过的才算欧拉路径\n",
    "        if len(self.nodes) == len(self.pairs) + 1:\n",
    "            self.exist = True\n",
    "        return\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        nodes= set()\n",
    "\n",
    "        for a, b in adjacentPairs:\n",
    "            nodes.add(a)\n",
    "            nodes.add(b)\n",
    "        nodes = sorted(nodes)\n",
    "        ind = {num: i for i, num in enumerate(nodes)}\n",
    "        pairs = [[ind[x], ind[y]] for x, y in adjacentPairs]\n",
    "        n = len(nodes)\n",
    "        ruler = UnDirectedEulerPath(n, pairs)\n",
    "        return [nodes[x] for x in ruler.nodes]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        connect = defaultdict(set)\n",
    "        for a,b in adjacentPairs:\n",
    "            connect[a].add(b)\n",
    "            connect[b].add(a)\n",
    "        point = min(connect.keys(), key=lambda x:(len(connect[x]), x))\n",
    "        explored = {point}\n",
    "        ans = [point]\n",
    "        cur = point\n",
    "        while len(ans) < len(connect.keys()):\n",
    "            cur = (connect[cur] - explored).pop()\n",
    "            explored.add(cur)\n",
    "            ans.append(cur)\n",
    "\n",
    "        res = self.restoreArray2(adjacentPairs)\n",
    "        for i in range(len(res)):\n",
    "            if res[i] != ans[i]:\n",
    "                print(i)\n",
    "                print(f'{res[i]} / {res[i-1]} / {ans[i]} / {ans[i-1]}')\n",
    "                break\n",
    "        return ans\n",
    "    \n",
    "    def restoreArray2(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        content = collections.defaultdict(set)\n",
    "        for item in adjacentPairs:\n",
    "            content[item[0]].add(item[1])\n",
    "            content[item[1]].add(item[0])\n",
    "\n",
    "        first = None\n",
    "        for key,value in content.items():\n",
    "            if len(value) == 1:\n",
    "                first = key\n",
    "                break\n",
    "        result = [first, content[first].pop()]\n",
    "        prev_key = result[0]\n",
    "        next_key = result[1]\n",
    "        while next_key:\n",
    "            current_neighbour = content[next_key]\n",
    "            current_neighbour.remove(prev_key)\n",
    "            prev_key = next_key\n",
    "            if current_neighbour:\n",
    "                next_key = current_neighbour.pop()\n",
    "                result.append(next_key)\n",
    "            else:\n",
    "                next_key = None\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self , i , j , dirr):\n",
    "        if dirr:\n",
    "            self.dirr1.append(i)\n",
    "        else:\n",
    "            self.dirr2.append(i)\n",
    "        for k in self.pair[i]:\n",
    "            if k != j:\n",
    "                self.dfs(k , i , dirr)\n",
    "                dirr = not dirr\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        self.pair = dict()\n",
    "        self.dirr1 = []\n",
    "        self.dirr2 = []\n",
    "        for pair in adjacentPairs:\n",
    "            if pair[0] in self.pair:\n",
    "                self.pair[pair[0]].append(pair[1])\n",
    "            else:\n",
    "                self.pair[pair[0]] = [pair[1]] ;\n",
    "            if pair[1] in self.pair:\n",
    "                self.pair[pair[1]].append(pair[0]) \n",
    "            else:\n",
    "                self.pair[pair[1]] = [pair[0]] ;\n",
    "        self.dfs(adjacentPairs[0][0] , 1e10 , 1)\n",
    "        return self.dirr2[::-1] + self.dirr1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        pairs=adjacentPairs\n",
    "        next_dic={}\n",
    "        #next_dic=defaultdict(list)\n",
    "\n",
    "        for p in pairs:\n",
    "            next_dic[p[0]]=next_dic.get(p[0],[])+[p[1]]\n",
    "            next_dic[p[1]]=next_dic.get(p[1],[])+[p[0]]\n",
    " \n",
    "        #print(next_dic)\n",
    "\n",
    "        def get_next(val):\n",
    "            nexts=next_dic[val]\n",
    "            if len(nexts)==0:\n",
    "                return None\n",
    "            next_dic[nexts[0]].remove(val)\n",
    "            next=nexts[0]\n",
    "            del next_dic[val][0]\n",
    "            return next\n",
    "            \n",
    "\n",
    "        def merge_nums(cur,cur_nums):\n",
    "            next=get_next(cur)\n",
    "            \n",
    "            #print(cur,next,next_dic)\n",
    "            if next is None:\n",
    "                return\n",
    "            else:\n",
    "                cur_nums.append(next)\n",
    "                merge_nums(next,cur_nums)\n",
    "\n",
    "        start=pairs[0][0]\n",
    "        nums1=[]\n",
    "        merge_nums(start,nums1)\n",
    "        \n",
    "        start = pairs[0][0]\n",
    "        nums2=[]\n",
    "        merge_nums(start, nums2)\n",
    "        nums1.reverse()\n",
    "        return nums1+[start]+nums2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        pairs=adjacentPairs\n",
    "        next_dic=defaultdict(list)\n",
    "\n",
    "        for p in pairs:\n",
    "            next_dic[p[0]].append(p[1])\n",
    "            next_dic[p[1]].append(p[0])\n",
    " \n",
    "        #print(next_dic)\n",
    "\n",
    "        def get_next(val):\n",
    "            nexts=next_dic[val]\n",
    "            if len(nexts)==0:\n",
    "                return None\n",
    "            next_dic[nexts[0]].remove(val)\n",
    "            next=nexts[0]\n",
    "            del next_dic[val][0]\n",
    "            return next\n",
    "            \n",
    "\n",
    "        def merge_nums(cur,cur_nums):\n",
    "            next=get_next(cur)\n",
    "            \n",
    "            #print(cur,next,next_dic)\n",
    "            if next is None:\n",
    "                return\n",
    "            else:\n",
    "                cur_nums.append(next)\n",
    "                merge_nums(next,cur_nums)\n",
    "\n",
    "        start=pairs[0][0]\n",
    "        nums1=[]\n",
    "        merge_nums(start,nums1)\n",
    "        \n",
    "        start = pairs[0][0]\n",
    "        nums2=[]\n",
    "        merge_nums(start, nums2)\n",
    "        nums1.reverse()\n",
    "        return nums1+[start]+nums2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        val_idx = {}\n",
    "        for idx, each in enumerate(adjacentPairs):\n",
    "            val_idx.setdefault(each[0], []).append(idx)\n",
    "            val_idx.setdefault(each[1], []).append(idx)\n",
    "\n",
    "        res = adjacentPairs[0]\n",
    "\n",
    "        def dfs(value, curr_idx, is_left):\n",
    "            idx_list = val_idx[value]\n",
    "            idx_list.remove(curr_idx)\n",
    "            if idx_list:\n",
    "                next_idx = idx_list[0]\n",
    "                next_arr = adjacentPairs[next_idx]\n",
    "                next_arr.remove(value)\n",
    "                if is_left:\n",
    "                    res.insert(0, next_arr[0])\n",
    "                else:\n",
    "                    res.append(next_arr[0])\n",
    "                dfs(next_arr[0], next_idx, is_left)\n",
    "\n",
    "        dfs(res[0], 0, True)\n",
    "        dfs(res[-1], 0, False)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        if len(adjacentPairs) == 1:\n",
    "            return adjacentPairs[0]\n",
    "        initial_item =adjacentPairs[0][0]\n",
    "        adjacent_info = defaultdict(list)\n",
    "        for pair in adjacentPairs:\n",
    "            adjacent_info[pair[0]].append(pair[1])\n",
    "            adjacent_info[pair[1]].append(pair[0])\n",
    "        def dfs(root, tmp, parent):\n",
    "\n",
    "            if len(adjacent_info[root]) == 1:\n",
    "                tmp.appendleft(root)\n",
    "                return\n",
    "            else:\n",
    "                tmp.appendleft(root)\n",
    "                adj1, adj2 = adjacent_info[root]\n",
    "                if adj1 == parent:\n",
    "                    dfs(adj2, tmp, root)\n",
    "                else:\n",
    "                    dfs(adj1, tmp, root)\n",
    "\n",
    "        def dfs2(root, tmp, parent):\n",
    "            if len(adjacent_info[root]) == 1:\n",
    "                if parent:\n",
    "                    tmp.append(root)\n",
    "                return\n",
    "            else:\n",
    "                if parent:\n",
    "                    tmp.append(root)\n",
    "                adj2, adj1 = adjacent_info[root]\n",
    "                if adj1 == parent:\n",
    "                    dfs2(adj2, tmp, root)\n",
    "                else:\n",
    "                    dfs2(adj1, tmp, root)\n",
    "        path = deque()\n",
    "\n",
    "        dfs(initial_item, path, None)\n",
    "        dfs2(initial_item, path, None)\n",
    "        return list(path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        pairs=adjacentPairs\n",
    "        next_dic={}\n",
    "\n",
    "        for p in pairs:\n",
    "            try:\n",
    "                next_dic[p[0]].append(p[1])\n",
    "            except:\n",
    "                next_dic[p[0]]=[p[1]]\n",
    "            try:\n",
    "                next_dic[p[1]].append(p[0])\n",
    "            except:\n",
    "                next_dic[p[1]]=[p[0]]\n",
    "\n",
    "        #print(next_dic)\n",
    "\n",
    "        def get_next(val):\n",
    "            nexts=next_dic[val]\n",
    "            if len(nexts)==0:\n",
    "                return None\n",
    "            next_dic[nexts[0]].remove(val)\n",
    "            next=nexts[0]\n",
    "            del next_dic[val][0]\n",
    "            return next\n",
    "            \n",
    "\n",
    "        def merge_nums(cur,cur_nums):\n",
    "            next=get_next(cur)\n",
    "            \n",
    "            #print(cur,next,next_dic)\n",
    "            if next is None:\n",
    "                return\n",
    "            else:\n",
    "                cur_nums.append(next)\n",
    "                merge_nums(next,cur_nums)\n",
    "\n",
    "        start=pairs[0][0]\n",
    "        nums1=[]\n",
    "        merge_nums(start,nums1)\n",
    "        \n",
    "        start = pairs[0][0]\n",
    "        nums2=[]\n",
    "        merge_nums(start, nums2)\n",
    "        nums1.reverse()\n",
    "        return nums1+[start]+nums2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        n = len(adjacentPairs) + 1\n",
    "        graph = {}\n",
    "        for a, b in adjacentPairs:\n",
    "            if(a not in graph):\n",
    "                graph[a] = []\n",
    "            graph[a].append(b)\n",
    "            if(b not in graph):\n",
    "                graph[b] = []\n",
    "            graph[b].append(a)\n",
    "        book = set()\n",
    "        def dfs(u):\n",
    "            for v in graph[u]:\n",
    "                if(v not in book):\n",
    "                    book.add(v)\n",
    "                    self.path.append(v)\n",
    "                    dfs(v)\n",
    "            return \n",
    "        l, r = adjacentPairs[0]\n",
    "        self.path = [l]\n",
    "        book.add(l)\n",
    "        book.add(r)\n",
    "        dfs(l)\n",
    "        left = self.path[::-1]\n",
    "        self.path = [r]\n",
    "        dfs(r)\n",
    "        right = self.path[:]\n",
    "        return left + right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adj: List[List[int]]) -> List[int]:\n",
    "        seen=set()\n",
    "        near=defaultdict(list)\n",
    "        ans=deque()\n",
    "        for (a, b) in adj:\n",
    "            near[a].append(b)\n",
    "            near[b].append(a)\n",
    "        def bfs(a, sign):\n",
    "            seen.add(a)           \n",
    "            if sign:\n",
    "                ans.append(a)\n",
    "            else:\n",
    "                ans.appendleft(a)\n",
    "            for b in near[a]:\n",
    "                if b in seen: continue\n",
    "                bfs(b, sign)           \n",
    "        for k in near:\n",
    "            ans.append(k)\n",
    "            seen.add(k)\n",
    "            bfs(near[k][0], True)\n",
    "            if len(near[k]) == 2:\n",
    "                bfs(near[k][1], False)\n",
    "            break\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        adj = defaultdict(list)\n",
    "        start = None\n",
    "        for a, b in adjacentPairs:\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "            if start is None:\n",
    "                start = a\n",
    "        visited = defaultdict(bool)\n",
    "        ans = []\n",
    "        def dfs(s, i, reverse=False):\n",
    "            visited[i] = True\n",
    "            if reverse:\n",
    "                ans.append(i)\n",
    "                for j in adj[i]:\n",
    "                    if not visited[j] and j != s:\n",
    "                        dfs(s, j, True)\n",
    "            else:\n",
    "                for j in adj[i]:\n",
    "                    if not visited[j] and j != s:\n",
    "                        dfs(s, j)\n",
    "                ans.append(i)\n",
    "        if len(adj[start]) == 2:\n",
    "            dfs(start, adj[start][0])\n",
    "            ans.append(start)\n",
    "            dfs(start, adj[start][1], True)\n",
    "        else:\n",
    "            ans.append(start)\n",
    "            dfs(start, adj[start][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        d = {}\n",
    "        for i in range(len(adjacentPairs)):\n",
    "            a = adjacentPairs[i][0]\n",
    "            b = adjacentPairs[i][1]\n",
    "\n",
    "            if a not in d:\n",
    "                d[a] = [b]\n",
    "            else:\n",
    "                d[a].append(b)\n",
    "            \n",
    "            if b not in d:\n",
    "                d[b] = [a]\n",
    "            else:\n",
    "                d[b].append(a)\n",
    "        \n",
    "        self.d = d\n",
    "\n",
    "        n = len(adjacentPairs) + 1\n",
    "        self.visited = set()\n",
    "        self.ans = [100000000] * (2*n)\n",
    "        index = n\n",
    "        start = adjacentPairs[0][0]\n",
    "        \n",
    "        def DFS(node, index):\n",
    "            self.visited.add(node)\n",
    "            self.ans[index] = node\n",
    "            sons = self.d[node]\n",
    "            for son in sons:\n",
    "                if son in self.visited:\n",
    "                    continue\n",
    "                else:\n",
    "                    if self.ans[index-1] == 100000000:\n",
    "                        DFS(son, index-1)\n",
    "                        continue\n",
    "                    if self.ans[index+1] == 100000000:\n",
    "                        DFS(son, index+1)\n",
    "                        continue\n",
    "        \n",
    "        DFS(start, index)\n",
    "        start_idx = 2 * n + 1\n",
    "        end_idx = -1\n",
    "        for i in range(len(self.ans)):\n",
    "            if self.ans[i] != 100000000:\n",
    "                start_idx = min(start_idx, i)\n",
    "                end_idx = max(end_idx, i)\n",
    "        \n",
    "        ans = self.ans[start_idx:end_idx + 1]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        n = len(adjacentPairs)+1\n",
    "        ans = collections.deque()\n",
    "        vDict=collections.defaultdict(list)\n",
    "        vset=set()\n",
    "        for v1,v2 in adjacentPairs:\n",
    "            vDict[v1].append([v1,v2])\n",
    "            vDict[v2].append([v1,v2])\n",
    "        def dfs(key):\n",
    "            for v1,v2 in vDict[key]:\n",
    "                if not vset:\n",
    "                    ans.append(v1)\n",
    "                    ans.append(v2)\n",
    "                    vset.add(v1)\n",
    "                    vset.add(v2)\n",
    "                    if v2==key:\n",
    "                        dfs(v1)\n",
    "                    else:\n",
    "                        dfs(v2)\n",
    "                if v1 in vset:\n",
    "                    if v2 in vset:\n",
    "                        continue\n",
    "                    else:\n",
    "                        if ans[0]==v1:\n",
    "                            ans.appendleft(v2)\n",
    "                        else:\n",
    "                            ans.append(v2)\n",
    "                        vset.add(v2)\n",
    "                        dfs(v2)\n",
    "                        continue\n",
    "                if v2 in vset:\n",
    "                    if ans[0]==v2:\n",
    "                        ans.appendleft(v1)\n",
    "                    else:\n",
    "                        ans.append(v1)\n",
    "                    vset.add(v1)\n",
    "                    dfs(v1)\n",
    "                    continue\n",
    "        dfs(adjacentPairs[0][0])\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        n = len(adjacentPairs)+1\n",
    "        ans = collections.deque()\n",
    "        vDict=collections.defaultdict(list)\n",
    "        vset=set()\n",
    "        for v1,v2 in adjacentPairs:\n",
    "            vDict[v1].append([v1,v2])\n",
    "            vDict[v2].append([v1,v2])\n",
    "        def dfs(key):\n",
    "            for v1,v2 in vDict[key]:\n",
    "                if not vset:\n",
    "                    ans.append(v1)\n",
    "                    ans.append(v2)\n",
    "                    vset.add(v1)\n",
    "                    vset.add(v2)\n",
    "                    if v2==key:\n",
    "                        dfs(v1)\n",
    "                    else:\n",
    "                        dfs(v2)\n",
    "                if v1 in vset:\n",
    "                    if v2 in vset:\n",
    "                        continue\n",
    "                    else:\n",
    "                        if ans[0]==v1:\n",
    "                            ans.appendleft(v2)\n",
    "                        else:\n",
    "                            ans.append(v2)\n",
    "                        vset.add(v2)\n",
    "                        dfs(v2)\n",
    "                        continue\n",
    "                if v2 in vset:\n",
    "                    if ans[0]==v2:\n",
    "                        ans.appendleft(v1)\n",
    "                    else:\n",
    "                        ans.append(v1)\n",
    "                    vset.add(v1)\n",
    "                    dfs(v1)\n",
    "                    continue\n",
    "        dfs(adjacentPairs[0][0])\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        class Node:\n",
    "            def __init__(self, x):\n",
    "                self.val = x\n",
    "                self.left = None\n",
    "                self.right = None\n",
    "\n",
    "            def reverse(self, rtype=\"both\"):\n",
    "                left = self.left\n",
    "                right = self.right\n",
    "                if rtype != 'left' and right:\n",
    "                    right.reverse('right')\n",
    "                if rtype != 'right' and left:\n",
    "                    left.reverse('left')\n",
    "                self.left, self.right = right, left\n",
    "\n",
    "        n = len(adjacentPairs) + 1\n",
    "        nodes = {}\n",
    "        for u, v in adjacentPairs:\n",
    "            if u not in nodes:\n",
    "                nodes[u] = Node(u)\n",
    "            if v not in nodes:\n",
    "                nodes[v] = Node(v)\n",
    "            if not nodes[u].right:\n",
    "                if nodes[v].left:\n",
    "                    nodes[v].reverse()\n",
    "                nodes[u].right = nodes[v]\n",
    "                nodes[v].left = nodes[u]\n",
    "            else:\n",
    "                if nodes[v].right:\n",
    "                    nodes[v].reverse()\n",
    "                nodes[u].left = nodes[v]\n",
    "                nodes[v].right = nodes[u]\n",
    "\n",
    "        res = []\n",
    "        visited = set()\n",
    "        for num in nodes:\n",
    "            if num not in visited:\n",
    "                node = nodes[num]\n",
    "                while node.left:\n",
    "                    node = node.left\n",
    "                while node:\n",
    "                    res.append(node.val)\n",
    "                    visited.add(node.val)\n",
    "                    node = node.right\n",
    "        return res\n",
    "        \n",
    "        # par, rank = list(range(n)), [0]*n\n",
    "\n",
    "        # def find(x):\n",
    "        #     if par[x] != x:\n",
    "        #         par[x] = find(par[x])\n",
    "        #     reutrn par[x]\n",
    "\n",
    "        # def unite(x, y):\n",
    "        #     x = find(x)\n",
    "        #     y = find(y)\n",
    "        #     if rank[x] < rank[y]:\n",
    "        #         par[x] = par[y]\n",
    "        #     else:\n",
    "        #         par[y] = par[x]\n",
    "        #         rank[x] += 1\n",
    "        \n",
    "        # def isSame(x, y):\n",
    "        #     return find(x) == find(y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def KeyElement(elem) :\n",
    "    return elem[1]\n",
    "\n",
    "def IterationSearch(dict, ret, start, previous) :\n",
    "    \n",
    "    local = dict.get(start)\n",
    "    #print(start, previous, local)\n",
    "    if len(local) < 2 :\n",
    "        return\n",
    "    else :\n",
    "        if local[0] != previous :\n",
    "            ret.append(local[0])\n",
    "            IterationSearch(dict, ret, local[0], start)\n",
    "        else :\n",
    "            ret.append(local[1])\n",
    "            IterationSearch(dict, ret, local[1], start)\n",
    "    return\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        adjacentPairs.sort(key=KeyElement)\n",
    "        #print(adjacentPairs)\n",
    "        store = {}\n",
    "        for i in adjacentPairs :\n",
    "            kk = store.get(i[0])\n",
    "            if kk == None :\n",
    "                store.update({i[0] : [i[1]]})\n",
    "            else :\n",
    "                kk.append(i[1])\n",
    "            kk = store.get(i[1])\n",
    "            if kk == None :\n",
    "                store.update({i[1] : [i[0]]})\n",
    "            else :\n",
    "                kk.append(i[0])\n",
    "        #tmp = dict.items()\n",
    "        #print(store)\n",
    "        for start in store.keys() :\n",
    "            if len(store.get(start)) < 2 :\n",
    "                break\n",
    "\n",
    "        ret = []\n",
    "        ret.append(start)\n",
    "        ret.extend(store.get(start))\n",
    "\n",
    "        IterationSearch(store, ret, ret[1], start)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def KeyElement(elem) :\n",
    "    return elem[1]\n",
    "\n",
    "def IterationSearch(dict, ret, start, previous) :\n",
    "    \n",
    "    local = dict.get(start)\n",
    "    print(start, previous, local)\n",
    "    if len(local) < 2 :\n",
    "        return\n",
    "    else :\n",
    "        if local[0] != previous :\n",
    "            ret.append(local[0])\n",
    "            IterationSearch(dict, ret, local[0], start)\n",
    "        else :\n",
    "            ret.append(local[1])\n",
    "            IterationSearch(dict, ret, local[1], start)\n",
    "    return\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        adjacentPairs.sort(key=KeyElement)\n",
    "        print(adjacentPairs)\n",
    "        store = {}\n",
    "        for i in adjacentPairs :\n",
    "            kk = store.get(i[0])\n",
    "            if kk == None :\n",
    "                store.update({i[0] : [i[1]]})\n",
    "            else :\n",
    "                kk.append(i[1])\n",
    "            kk = store.get(i[1])\n",
    "            if kk == None :\n",
    "                store.update({i[1] : [i[0]]})\n",
    "            else :\n",
    "                kk.append(i[0])\n",
    "        #tmp = dict.items()\n",
    "        print(store)\n",
    "        for start in store.keys() :\n",
    "            if len(store.get(start)) < 2 :\n",
    "                break\n",
    "\n",
    "        ret = []\n",
    "        ret.append(start)\n",
    "        ret.extend(store.get(start))\n",
    "\n",
    "        IterationSearch(store, ret, ret[1], start)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnDirectedEulerPath:\n",
    "    def __init__(self, n, pairs):\n",
    "        # 数组形式存储的有向连接关系\n",
    "        self.n = n\n",
    "        self.pairs = pairs\n",
    "        # 欧拉路径上的每条边和经过的几点\n",
    "        self.paths = list()\n",
    "        self.nodes = list()\n",
    "        self.exist = False\n",
    "        self.get_euler_path()\n",
    "        return\n",
    "\n",
    "    def get_euler_path(self):\n",
    "        # 存顶点的出入度\n",
    "        degree = [0]*self.n\n",
    "        # 存储图关系\n",
    "        edge = [dict() for _ in range(self.n)]\n",
    "        for i, j in self.pairs:\n",
    "            degree[i] += 1\n",
    "            degree[j] += 1\n",
    "            edge[i][j] = edge[i].get(j, 0) + 1\n",
    "            edge[j][i] = edge[j].get(i, 0) + 1\n",
    "        edge_dct = [deque(sorted(dt)) for dt in edge]  # 从小到大进行序号遍历\n",
    "        # 寻找起始节点\n",
    "        starts = []\n",
    "        zero = 0\n",
    "        for i in range(self.n):\n",
    "            # 如果有节点出度比入度恰好多 1，那么只有它才能是起始\n",
    "            if degree[i] % 2:\n",
    "                starts.append(i)\n",
    "            else:\n",
    "                zero += 1\n",
    "        del degree\n",
    "\n",
    "        # 不存在欧拉路径\n",
    "        if not len(starts) == 2:\n",
    "            if zero != self.n:\n",
    "                return\n",
    "            starts = [0]\n",
    "\n",
    "        # 使用迭代版本Hierholzer算法计算\n",
    "        stack = [starts[0]]\n",
    "        while stack:\n",
    "            current = stack[-1]\n",
    "            next_node = None\n",
    "            while edge_dct[current]:\n",
    "                if not edge[current][edge_dct[current][0]]:\n",
    "                    edge_dct[current].popleft()\n",
    "                    continue\n",
    "                nex = edge_dct[current][0]\n",
    "                if edge[current][nex]:\n",
    "                    edge[current][nex] -= 1\n",
    "                    edge[nex][current] -= 1\n",
    "                    next_node = nex\n",
    "                    stack.append(next_node)\n",
    "                    break\n",
    "            if next_node is None:\n",
    "                self.nodes.append(current)\n",
    "                if len(stack) > 1:\n",
    "                    pre = stack[-2]\n",
    "                    self.paths.append([pre, current])\n",
    "                stack.pop()\n",
    "        self.paths.reverse()\n",
    "        self.nodes.reverse()\n",
    "        # 注意判断所有边都经过的才算欧拉路径\n",
    "        if len(self.nodes) == len(self.pairs) + 1:\n",
    "            self.exist = True\n",
    "        return\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        nodes= set()\n",
    "\n",
    "        for a, b in adjacentPairs:\n",
    "            nodes.add(a)\n",
    "            nodes.add(b)\n",
    "        nodes = sorted(nodes)\n",
    "        ind = {num: i for i, num in enumerate(nodes)}\n",
    "        pairs = [[ind[x], ind[y]] for x, y in adjacentPairs]\n",
    "        n = len(nodes)\n",
    "        ruler = UnDirectedEulerPath(n, pairs)\n",
    "        return [nodes[x] for x in ruler.nodes]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        d = defaultdict(list)\n",
    "        for x in adjacentPairs:\n",
    "            d[x[0]].append(x[1])\n",
    "            d[x[1]].append(x[0])\n",
    "        # print(d)\n",
    "        # print(v)\n",
    "        ans = []\n",
    "        start = 10 ** 5 + 1\n",
    "        for i in d.keys():\n",
    "            if len(d[i]) == 1:\n",
    "                start = i\n",
    "                break\n",
    "        vis = {}\n",
    "        self.dfs(d,start,ans,vis)\n",
    "        return ans\n",
    "    def dfs(self,d,i,ans,vis):\n",
    "        if i in vis:\n",
    "            return\n",
    "        vis[i] = True\n",
    "        ans.append(i)\n",
    "        for j in d[i]:\n",
    "            self.dfs(d,j,ans,vis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        ans_map,sp={},0\n",
    "        hmap=defaultdict(list)\n",
    "        for a,b in adjacentPairs:\n",
    "            hmap[a].append(b)\n",
    "            hmap[b].append(a)\n",
    "        for i,j in hmap.items():\n",
    "            if len(j)==1:\n",
    "                sp=i\n",
    "                break\n",
    "        ans_map[sp]=\"p\"\n",
    "        self.dfs(sp,hmap,ans_map)\n",
    "        return list(ans_map.keys())\n",
    "    def dfs(self,node,hmap,ans_map):\n",
    "        for it in hmap[node]:\n",
    "            if it not in ans_map:\n",
    "                ans_map[it]=\"p\"\n",
    "                self.dfs(it,hmap,ans_map)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        # 构建相邻的节点关系\n",
    "        pair = defaultdict(list)\n",
    "        for i in adjacentPairs:\n",
    "            pair[i[0]].append(i[1])\n",
    "            pair[i[1]].append(i[0])\n",
    "\n",
    "        # 找到只有一个节点相邻的节点，作为头结点\n",
    "        start = 0\n",
    "        for i in pair:\n",
    "            if len(pair[i]) == 1:\n",
    "                start = i\n",
    "                break\n",
    "\n",
    "        # 用递归构建数组\n",
    "        res = [start]\n",
    "\n",
    "        def dfs(left: int):\n",
    "            if not pair[left]:\n",
    "                return\n",
    "            nextI = pair[left][0]\n",
    "            # 必须要删除已经用过的节点，否则会进入死循环\n",
    "            pair[nextI].remove(left)\n",
    "            res.append(nextI)\n",
    "            dfs(nextI)\n",
    "\n",
    "        dfs(start)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        val_idx = {}\n",
    "        val_idx_set = {}\n",
    "        for idx, each in enumerate(adjacentPairs):\n",
    "            if each[0] in val_idx_set:\n",
    "                val_idx_set.pop(each[0])\n",
    "            else:\n",
    "                val_idx_set[each[0]] = idx\n",
    "            if each[1] in val_idx_set:\n",
    "                val_idx_set.pop(each[1])\n",
    "            else:\n",
    "                val_idx_set[each[1]] = idx\n",
    "            val_idx.setdefault(each[0], []).append(idx)\n",
    "            val_idx.setdefault(each[1], []).append(idx)\n",
    "\n",
    "        start_idx = list(val_idx_set.values())[0]\n",
    "        res = adjacentPairs[start_idx] if adjacentPairs[start_idx][0] in val_idx_set else [adjacentPairs[start_idx][1],\n",
    "                                                                                           adjacentPairs[start_idx][0]]\n",
    "\n",
    "        def dfs(value, curr_idx):\n",
    "            idx_list = val_idx[value]\n",
    "            idx_list.remove(curr_idx)\n",
    "            if idx_list:\n",
    "                next_idx = idx_list[0]\n",
    "                next_arr = adjacentPairs[next_idx]\n",
    "                next_arr.remove(value)\n",
    "                res.append(next_arr[0])\n",
    "                dfs(next_arr[0], next_idx)\n",
    "\n",
    "        dfs(res[-1], start_idx)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        def dfs(i, fa):\n",
    "            ans.append(i)\n",
    "            for j in g[i]:\n",
    "                if j != fa:\n",
    "                    dfs(j, i)\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        for a, b in adjacentPairs:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        i = next(i for i, v in g.items() if len(v) == 1)\n",
    "        ans = []\n",
    "        dfs(i, 1e6)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        graph = defaultdict(list)\n",
    "        graph_cnt = defaultdict(int)\n",
    "        \n",
    "        for item in adjacentPairs:\n",
    "            graph[item[0]].append(item[1])\n",
    "            graph[item[1]].append(item[0])\n",
    "            graph_cnt[item[0]] += 1\n",
    "            graph_cnt[item[1]] += 1\n",
    "            \n",
    "        for k in graph_cnt:\n",
    "            if graph_cnt[k] == 1:\n",
    "                start = k\n",
    "                \n",
    "        ans = [start]\n",
    "        pre = start\n",
    "        cur = graph[start][0]\n",
    "        \n",
    "        def dfs(cur, pre):\n",
    "            ans.append(cur)\n",
    "            for num in graph[cur]:\n",
    "                if num != pre:\n",
    "                    dfs(num, cur)\n",
    "                    \n",
    "        dfs(cur, pre)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.graph = defaultdict(list)\n",
    "\n",
    "    def restoreArray(self, adjacentPairs: list[list[int]]) -> List[int]:\n",
    "        \n",
    "        for x, y in adjacentPairs:\n",
    "            self.graph[x].append(y)\n",
    "            self.graph[y].append(x)\n",
    "        \n",
    "        root = None\n",
    "        for num in self.graph:\n",
    "            if len(self.graph[num]) == 1:\n",
    "                root = num\n",
    "                break\n",
    "\n",
    "        ans = []\n",
    "        self.dfs(root, None, ans)\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, node, prev, ans):\n",
    "        ans.append(node)\n",
    "        for neighbor in self.graph[node]:\n",
    "            if neighbor != prev:\n",
    "                self.dfs(neighbor, node, ans)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
